package com.gxc.tree;

/**
 * 叉树节点间的最大距离问题
 从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，
 到达节点b时路径上的节点个数叫作a到b的距离，
 那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。
 */
public class MaxDistance {

    public class Info {
        public int maxDistance;
        public int heighe;

        public Info(int maxDistance, int heighe) {
            this.maxDistance = maxDistance;
            this.heighe = heighe;
        }
    }

    /**
     * 以X为头结点的最大距离
     * @param x
     * @return
     */
    public Info treeMaxDistance(TreeBean x) {
        if (x == null) return new Info(0, 0);
        Info left = treeMaxDistance(x.left);
        Info right = treeMaxDistance(x.right);
        int p1 = left.maxDistance;
        int p2 = right.maxDistance;
        //+1 是加头结点
        int p3 = right.heighe + right.heighe+1;
        int max = Math.max(p3, Math.max(p1, p2));
        int height = Math.max(left.heighe, right.heighe) + 1;
        return new Info(max, height);
    }
}
